package com.code.leetcode._202503;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**Z字形变化，难度中等**/
public class ZCharConvert {

    public static void main(String[] args) {
        String s = "PAYPALISHIRING";
        System.out.println(convert(s,4));
    }
    static int N = 1010;
    static char[][] g = new char[N][N];
    static int[] idxs = new int[N];
    //模拟 算法
    public static String convert(String s, int m) {
        if ( m == 1 ) return s;
        int n = s.length();
        //讲idxs数组内容全部填充为0
        Arrays.fill(idxs,0);
        //遍历字符串的内容并放入相应的数组的位置
        for (int i = 0, j=0 , k =1; i < n; i++) {
            //将字符按照m行，进行一次向下排列
            g[j][idxs[j]++] = s.charAt(i);
            j += k;
            //到了第一行就开始正序
            if (j<0){
                j+=2;
                k=1;
            }else if (j == m){
                //最后一行就开始倒叙
                j -= 2;
                k = -1;
            }
        }
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < idxs[i]; j++) {
                sb.append(g[i][j]);
            }
        }
        return sb.toString();
    }

    //数学规律
    public static String convert1(String s,int r){
        int n = s.length();
        if (n == 1 || r == 1) return s;
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < r; i++) {
            if (i == 0 || i == r - 1) {
                int pos = i, offset = 2 * (r - 1);
                while (pos < n) {
                    sb.append(s.charAt(pos));
                    pos += offset;
                }
            } else {
                int pos1 = i, pos2 = 2 * r - i - 2;
                int offset = 2 * (r - 1);
                while (pos1 < n || pos2 < n) {
                    if (pos1 < n) {
                        sb.append(s.charAt(pos1));
                        pos1 += offset;
                    }
                    if (pos2 < n) {
                        sb.append(s.charAt(pos2));
                        pos2 += offset;
                    }
                }
            }
        }
        return sb.toString();
    }
    /**设 n 为字符串 s 的长度，r=numRows。对于 r=1（只有一行）或者 r≥n（只有一列）的情况，答案与 s 相同，
     * 我们可以直接返回 s。对于其余情况，考虑创建一个二维矩阵，然后在矩阵上按 Z 字形填写字符串 s，最后逐行
     * 扫描矩阵中的非空字符，组成答案。
     *根据题意，当我们在矩阵上填写字符时，会向下填写 r 个字符，然后向右上继续填写 r−2 个字符，最后回到第一
     * 行，因此 Z 字形变换的周期 t=r+r−2=2r−2，每个周期会占用矩阵上的 1+r−2=r−1 列。
     *因此我们有n/t个周期（最后一个周期视作完整周期），乘上每个周期的列数，得到矩阵的列数 c=⌈n/t]*(r-1)
     * 创建一个 r 行 c 列的矩阵，然后遍历字符串 s 并按 Z 字形填写。具体来说，设当前填写的位置为 (x,y)，
     * 即矩阵的 x 行 y 列。初始 (x,y)=(0,0)，即矩阵左上角。若当前字符下标 i 满足 imodt<r−1，则向下移动，
     * 否则向右上移动。**/
    public String convert2(String s, int numRows) {
        int n = s.length(), r = numRows;
        if (r == 1 || r >= n) {
            return s;
        }
        int t = r * 2 - 2;
        int c = (n + t - 1) / t * (r - 1);
        char[][] mat = new char[r][c];
        for (int i = 0, x = 0, y = 0; i < n; ++i) {
            mat[x][y] = s.charAt(i);
            if (i % t < r - 1) {
                ++x; // 向下移动
            } else {
                --x;
                ++y; // 向右上移动
            }
        }
        StringBuffer ans = new StringBuffer();
        for (char[] row : mat) {
            for (char ch : row) {
                if (ch != 0) {
                    ans.append(ch);
                }
            }
        }
        return ans.toString();
    }
    //压缩矩阵空间
    public String convert3(String s, int numRows) {
        int n = s.length(), r = numRows;
        if (r == 1 || r >= n) {
            return s;
        }
        StringBuffer[] mat = new StringBuffer[r];
        for (int i = 0; i < r; ++i) {
            mat[i] = new StringBuffer();
        }
        for (int i = 0, x = 0, t = r * 2 - 2; i < n; ++i) {
            mat[x].append(s.charAt(i));
            if (i % t < r - 1) {
                ++x;
            } else {
                --x;
            }
        }
        StringBuffer ans = new StringBuffer();
        for (StringBuffer row : mat) {
            ans.append(row);
        }
        return ans.toString();
    }
    //巧设 flag ，清晰图解
    /**
     * 字符串 s 是以 Z 字形为顺序存储的字符串，目标是按行打印。
     *设 numRows 行字符串分别为 s1, s2, … , sn，则容易发现：按顺序遍历字符串 s 时，每个字符 c 在
     * N 字形中对应的 行索引 先从 s1增大至 sn，再从 sn减小至 s1…… 如此反复。
     * 因此解决方案为：模拟这个行索引的变化，在遍历 s 中把每个字符填到正确的行 res[i]**/
    public String convert4(String s, int numRows) {
        if(numRows < 2) return s;
        List<StringBuilder> rows = new ArrayList<>();
        for(int i = 0; i < numRows; i++) rows.add(new StringBuilder());
        int i = 0, flag = -1;
        for(char c : s.toCharArray()) {
            rows.get(i).append(c);
            if(i == 0 || i == numRows -1) flag = - flag;
            i += flag;
        }
        StringBuilder res = new StringBuilder();
        for(StringBuilder row : rows) res.append(row);
        return res.toString();
    }

}
